package _18_剑指OfferII;

public class _092_剑指OfferII翻转字符 {

    // dp数组优化
    public int minFlipsMonoIncr(String s) {
        char[] chars = s.toCharArray();
        int one = 0;
        int two = 0;

        for (char aChar : chars) {
            if (aChar == '0') {
                two = Math.min(one, two) + 1;
            } else {
                two = Math.min(one, two);
                one++;
            }
        }
        return Math.min(one, two);
    }

    public int minFlipsMonoIncr1(String s) {
        char[] chars = s.toCharArray();
        int length = chars.length;
        int[][] dp = new int[length][2];
        // 初始化dp数据
        if (chars[0] == '0') {
            dp[0][0] = 0;
            dp[0][1] = 1;
        } else {
            dp[0][0] = 1;
            dp[0][1] = 0;
        }

        for (int i = 1; i < length; i++) {
            if (chars[i] == '0') {
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + 1;
            } else {
                dp[i][0] = dp[i - 1][0] + 1;
                dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]);
            }
        }
        return Math.min(dp[length - 1][0], dp[length - 1][1]);
    }

}
